package com.liyuncong.algorithm.algorithm_kmeans;

import java.util.ArrayList;
import java.util.List;

import com.liyuncong.algorithm.algorithm_kmeans.entity.Cluster;
import com.liyuncong.algorithm.algorithm_kmeans.entity.Vectors;
import com.liyuncong.algorithm.algorithm_kmeans.util.ClusterUtil;
import com.liyuncong.algorithm.algorithm_similarity.entity.Vector;
/**
 * kmean算法实现: 算法的输入是一组向量
 * @author yuncong
 *
 */
public class Kmeans {
	/**
	 * kmeans聚类算法实现
	 * @param k
	 * @param vectors
	 * @return
	 */
	public List<Cluster> cluster(int k, Vectors vectors, float sse) {
		// 获得初始化聚类中心
		List<Vector> centers = this.chooseInitialCenters(k, vectors);
		
		List<Cluster> clusters = null;
		
		while (true) {
			System.out.println(".");
			clusters = this.oneIteration(centers, vectors);
			if (ClusterUtil.computeSSE(clusters) <= sse) {
				break;
			}
			centers = this.getCenters(clusters);
			// 测试
			for(Vector vector : centers) {
				ClusterUtil.printVector(vector);
			}
			try {
				Thread.sleep(1000);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		
		return clusters;
	}
	
	/**
	 * 选取初始的k个聚类中心;
	 * 默认实现为选取前k个向量；
	 * @param k
	 * @param vectors
	 * @return
	 */
	private List<Vector> chooseInitialCenters(int k, Vectors vectors) {
		List<Vector> centers = new ArrayList<Vector>();
		for(int i = 0; i < k; i++) {
			centers.add(vectors.ValueOf(i));
		}
		return centers;
	}
	
	/**
	 * 根据聚类中心，对向量进行聚类；
	 * 只一次迭代
	 * @param centers
	 * @param vectors
	 * @return
	 */
	private List<Cluster> oneIteration(List<Vector> centers, Vectors vectors) {
		List<Cluster> clusters = new ArrayList<Cluster>();
		
		// 聚类中心个数
		int k = centers.size();
		
		List<List<Vector>> clusterlList = new ArrayList<>();
		// 初始化保存聚类的list
		for(int i = 0; i < k; i++) {
			clusterlList.add(new ArrayList<Vector>());
		}
		
		int vectorNum = vectors.size();
		// 把每一个向量分给离它最近的那个聚类
		for(int i = 0; i < vectorNum; i++) {
			// 当前待分配向量
			Vector currentVector = vectors.ValueOf(i);
			// 保存着最大的相似度
			float similarity = Integer.MAX_VALUE;
			// 保存着最近的聚类的索引
			int clusterIndex = 0;
			for(int j = 0; j < k; j++) {
				if (currentVector.distanceTo(centers.get(j)) < similarity) {
					clusterIndex = j;
					similarity = vectors.ValueOf(i).distanceTo(centers.get(j));
				}
			}
			clusterlList.get(clusterIndex).add(currentVector);
		}
		
		//获得聚类
		for(int i = 0; i < k; i++) {
			List<Vector> elementList = clusterlList.get(i);
			clusters.add(new Cluster(elementList));
		}
		
		return clusters;
	}
	
	/**
	 * 获得所有聚类的中心
	 * @param clusters
	 * @return
	 */
	private List<Vector> getCenters(List<Cluster> clusters) {
		List<Vector> centers = new ArrayList<>();
		for(Cluster cluster : clusters) {
			centers.add(cluster.getCenter());
		}
		return centers;
	}
}
